/*
 * @lc app=leetcode.cn id=438 lang=cpp
 *
 * [438] 找到字符串中所有字母异位词
 */

// @lc code=start
class Solution
{
public:
    vector<int> findAnagrams(string s, string p)
    {
        //找到所有异位词子串 返回子串开始位置
        //我想到的就是直接遍历所有位置 暴力解法 不过好像可以用滑动窗口
        if (s.size() < p.size())
        {
            return {};
        }
        vector<int> res;
        unordered_map<char, int> a;
        for (char c : p)
        {
            a[c]++;
        }
        int left = 0;
        int right = p.size() - 1; //初始位置
        //保证首字符在p内 避免前期无用操作
        while (right < s.size() && !a.count(s[left]))
        {
            left++;
            right++;
        }
        //对当前窗口内操作
        for (int i = left; i <= right; i++)
        {
            a[s[i]]--;
        }
        while (right < s.size())
        {
            bool istrue = true;
            for (auto it = a.begin(); it != a.end(); it++)
            {
                if (it->second != 0)
                {
                    istrue = false;
                    break;
                }
            }
            if (istrue)
            {
                res.emplace_back(left);
            }
            //滑动窗口
            a[s[left++]]++;
            a[s[++right]]--;
        }
        return res;
    }
};
// @lc code=end
